
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <ctype.h>

#include "xmlscanner.h"

//TODO: break parser into header/source
//TODO: handle <?xml tags
//TODO: handle <! -- comments
//TODO: better error messages (line, char, context) (could be done outside parser)



#define CHAR_TAGSTART(c) ((c)=='<')
#define CHAR_CLOSE(c) ((c)=='/')
#define CHAR_TAGEND(c) ((c)=='>')
#define CHAR_EQUALS(c) ((c)=='=')
#define CHAR_SPACE(c) (isspace(c))
#define CHAR_ID(c) (((c)=='-')||((c)==':')||((c)=='_')||((c)=='.')||isalnum(c))
#define CHAR_QUOTE(c) ((c)=='\"')

XMLScanner::XMLScanner( char const * buf, size_t size )
{
  buf_ = buf;
  end_ = buf+size;
  unsigned char const * tmp = reinterpret_cast< unsigned char const * >( buf );
  if( size > 2 && tmp[0] == 0xef && tmp[1] == 0xbb && tmp[2] == 0xbf ) {
    //  this is a UTF-8 file with the "Unicode" marker char up front
    buf_ += 3;
  }
  stackPtr_ = 0;
  stack_[0].kind = Token::Error;
  stack_[0].key = 0;
  stack_[0].keySize = 0;
  stack_[0].value = 0;
  stack_[0].valueSize = 0;
}

XMLScanner::~XMLScanner()
{
  //  there's nothing to de-allocate!
}

#define SKIP_SPACE(x) { \
  while( buf_ < end_ && CHAR_SPACE( *buf_ ) ) { \
    ++buf_; \
  } \
  if( buf_ == end_ ) { \
    error = "unterminated " #x ; \
    goto return_error; \
  } \
}


bool XMLScanner::nextToken( XMLScanner::Token * outToken )
{
  if( buf_ == end_ ) {
    outToken->kind = Token::EndOfFile;
    outToken->key = 0;
    outToken->keySize = 0;
    outToken->value = 0;
    outToken->valueSize = 0;
    return false;
  }

  char const * error = "unhandled error";

  bool allowTagOrClose = false;
  bool allowCDATA = false;
  bool allowWhitespace = false;
  bool allowAttribute = false;

  switch( stack_[stackPtr_].kind ) {
  case Token::Whitespace:
    allowTagOrClose = true;
    allowCDATA = true;
    break;
  case Token::CDATA:
    allowTagOrClose = true;
    allowWhitespace = true;
    break;
  case Token::Tag:
  case Token::Attribute:
    allowAttribute = true;
    break;
  default:
  case Token::EndOfFile:
    assert( !"internal error in XMLScanner" );
  case Token::Error:
  case Token::Close:
    allowTagOrClose = true;
    allowCDATA = true;
    allowWhitespace = true;
    break;
  }

finished_a_tag:

  char const * beg = buf_;

  if( allowTagOrClose ) {
    if( *buf_ == '<' ) {
      //  Tag or Close
      ++buf_;
      bool isClose = false;
      if( CHAR_CLOSE( *buf_ ) ) {
        //  Close
        isClose = true;
        ++buf_;
      }
      beg = buf_;
      if( buf_ >= end_ || !CHAR_ID( *buf_ ) ) {
        error = "unterminated tag";
        goto return_error;
      }
      while( buf_ < end_ && CHAR_ID( *buf_ ) ) {
        ++buf_;
      }
      if( buf_ == beg ) {
        error = "unterminated tag";
        goto return_error;
      }
      if( isClose ) {
        if( stackPtr_ == 0 ) {
          error = "close tag with no open";
          goto return_error;
        }
        --stackPtr_;
        if( buf_-beg != stack_[stackPtr_].keySize || memcmp( beg, stack_[stackPtr_].key, buf_-beg ) ) {
          //  TODO: a lenient parser would auto-close some number of tags if necessary, 
          //  and ignore closes that have no tags on the stack.
          error = "mis-matching close tag";
          goto return_error;
        }
        stack_[stackPtr_].kind = Token::Close;
        stack_[stackPtr_].value = beg;
        stack_[stackPtr_].valueSize = buf_-beg;
        //  retain the other values from the Tag, as it points to the right tag name (and that's useful)
        SKIP_SPACE(tag);
        if( !CHAR_TAGEND( *buf_ ) ) {
          error = "improper close tag format";
          goto return_error;
        }
        ++buf_;
      }
      else {
        if( stackPtr_ == StackDepth-1 ) {
          error = "too deep tag nesting";
          goto return_error;
        }
        stack_[stackPtr_].kind = Token::Tag;
        stack_[stackPtr_].key = beg;
        stack_[stackPtr_].keySize = buf_-beg;
        stack_[stackPtr_].value = 0;
        stack_[stackPtr_].valueSize = 0;
        ++stackPtr_;
        stack_[stackPtr_] = stack_[stackPtr_-1];
      }
      goto return_ok;
    }
  }
  assert( !(allowAttribute && allowWhitespace) );
  if( allowWhitespace ) {
    while( buf_ < end_ && CHAR_SPACE( *buf_ ) ) {
      ++buf_;
    }
    if( buf_ > beg ) {
      stack_[stackPtr_].kind = Token::Whitespace;
      stack_[stackPtr_].key = 0;
      stack_[stackPtr_].keySize = 0;
      stack_[stackPtr_].value = beg;
      stack_[stackPtr_].valueSize = buf_-beg;
      goto return_ok;
    }
  }
  assert( !(allowAttribute && allowCDATA) );
  if( allowCDATA ) {
    //  CDATA
    char const * space = 0;
    while( buf_ < end_ ) {
      if( CHAR_SPACE( *buf_ ) && !space ) {
        space = buf_;
      }
      else if( CHAR_TAGSTART( *buf_ ) ) {
        if( space ) {
          buf_ = space;
        }
        break;
      }
      else {
        space = 0;
      }
      ++buf_;
    }
    stack_[stackPtr_].kind = Token::CDATA;
    stack_[stackPtr_].key = 0;
    stack_[stackPtr_].keySize = 0;
    stack_[stackPtr_].value = beg;
    stack_[stackPtr_].valueSize = buf_-beg;
    goto return_ok;
  }
  //  allowAttribute really means we're inside an open tag
  if( allowAttribute ) {
    SKIP_SPACE(attribute);
    beg = buf_;
    if( CHAR_CLOSE( *buf_ ) ) {
      if( ++buf_ == end_ ) {  //  skip close
        error = "unterminated tag";
        goto return_error;
      }
      if( !CHAR_TAGEND( *buf_ ) ) {
        error = "XML syntax error (bracket must follow closing slash)";
        goto return_error;
      }
      ++buf_; // skip tagend
      assert( stackPtr_ > 0 );
      if( stackPtr_ == 0 ) {
        error = "internal error (self-closing tag with no stack)";
        goto return_error;
      }
      --stackPtr_;
      stack_[stackPtr_].kind = Token::Close;
      stack_[stackPtr_].value = buf_-2;
      stack_[stackPtr_].valueSize = 2;
      goto return_ok;
    }
    else if( CHAR_TAGEND( *buf_ ) ) {
      ++buf_;
      allowAttribute = false;
      allowCDATA = true;
      allowWhitespace = true;
      allowTagOrClose = true;
      goto finished_a_tag;
    }
    else if( !CHAR_ID( *buf_ ) ) {
      error = "illegal attribute name";
      goto return_error;
    }
    stack_[stackPtr_].key = buf_;
    // gather attribute identifier
    while( buf_ < end_ && CHAR_ID( *buf_ ) ) {
      ++buf_;
    }
    stack_[stackPtr_].keySize = buf_ - stack_[stackPtr_].key;
    if( buf_ == end_ ) {
      error = "unterminated attribute";
      goto return_error;
    }
    SKIP_SPACE(attribute);
    if( !CHAR_EQUALS( *buf_ ) ) {
      error = "expected attribute equals sign";
      goto return_error;
    }
    ++buf_; // skip equals
    SKIP_SPACE(attribute);
    if( !CHAR_QUOTE( *buf_ ) ) {
      error = "expected attribute quote";
      goto return_error;
    }
    ++buf_; // skip quote
    stack_[stackPtr_].value = buf_;
    // gather attribute value
    while( buf_ < end_ && !CHAR_QUOTE( *buf_ ) ) {
      ++buf_;
    }
    if( buf_ == end_ ) {
      error = "unterminated attribute value";
      goto return_error;
    }
    stack_[stackPtr_].valueSize = buf_ - stack_[stackPtr_].value;
    stack_[stackPtr_].kind = Token::Attribute;
    ++buf_; // skip last quote
    goto return_ok;
  }

  error = "XML format error";

return_error:
  stack_[stackPtr_].kind = Token::Error;
  stack_[stackPtr_].key = beg;
  stack_[stackPtr_].keySize = buf_-beg;
  stack_[stackPtr_].value = error;
  stack_[stackPtr_].valueSize = strlen( error );
  *outToken = stack_[stackPtr_];
  return false;

return_ok:
  *outToken = stack_[stackPtr_];
  return true;
}

size_t XMLScanner::depth() const
{
  return stackPtr_;
}

XMLScanner::Token const * XMLScanner::tokenAtDepth( size_t depth )
{
  assert( depth <= stackPtr_ );
  return &stack_[stackPtr_-depth];
}


#if 0

int main( int argc, char * argv[] ) 
{
  if( argc < 2 ) {
    fprintf( stderr, "usage: xmlpp file ...\n" );
    return 1;
  }
  int errors = 0;
  for( int i = 1; i < argc; ++i ) {
    FILE * f = fopen( argv[i], "rb" );
    if( f == NULL ) {
      fprintf( stderr, "xmlpp: %s: cannot open\n", argv[i] );
      return 1;
    }
    fseek( f, 0, 2 );
    size_t len = ftell( f );
    fseek( f, 0, 0 );
    char * ptr = (char *)malloc( len );
    fread( ptr, 1, len, f );
    fclose( f );
    XMLScanner::Token t;
    XMLScanner scanner( ptr, len );
    bool inTag = false;
    while( scanner.nextToken( &t ) ) {
      switch( t.kind ) {
      case XMLScanner::Token::Error:
        assert( !"this should not happen" );
        break;
      case XMLScanner::Token::Whitespace:
        fprintf( stdout, "Whitespace\n" );
        break;
      case XMLScanner::Token::CDATA:
        fprintf( stdout, "CDATA: %.*s\n", t.valueSize, t.value );
        break;
      case XMLScanner::Token::Tag:
        fprintf( stdout, "Tag: %.*s\n", t.keySize, t.key );
        break;
      case XMLScanner::Token::Attribute:
        fprintf( stdout, "Attribute: %.*s = \"%.*s\"\n", t.keySize, t.key, t.valueSize, t.value );
        break;
      case XMLScanner::Token::Close:
        fprintf( stdout, "Close tag: %.*s\n", t.keySize, t.key );
        break;
      case XMLScanner::Token::EndOfFile:
        assert( !"this should not happen" );
        break;
      }
    }
    if( t.kind == XMLScanner::Token::Error ) {
      fprintf( stderr, "error: %.*s at '%.*s'\n", t.valueSize, t.value, t.keySize, t.key );
      ++errors;
    }
    free( ptr );
  }
  return errors;
}

#endif


XMLDom::XMLDom( char const * buffer, size_t size, void (*freeFunc)( char const * ) )
{
  buffer_ = buffer;
  size_ = size;
  freeFunc_ = freeFunc;
  root_ = 0;
  error_ = 0;
  nodes_ = 0;
  numBlocks_ = 0;
  nextNode_ = 0;
  nodesLeft_ = 0;
  XMLScanner s( buffer_, size_ );
  parse( 0, &root_, s );
}

XMLDom::~XMLDom()
{
  for( size_t i = 0; i < numBlocks_; ++i ) {
    delete[] nodes_[i];
  }
  if( freeFunc_ ) {
    freeFunc_( buffer_ );
  }
}

XMLNode * XMLDom::root()
{
  return root_;
}

char const * XMLDom::error()
{
  return error_ ? error_->token_.value : 0;
}

void XMLDom::parse( XMLNode * parent, XMLNode ** root, XMLScanner & s )
{
  XMLScanner::Token t;
  while( s.nextToken( &t ) ) {
    switch( t.kind ) {
    case XMLScanner::Token::Attribute:
    case XMLScanner::Token::Whitespace:
    case XMLScanner::Token::CDATA:
      *root = newNode();
      (*root)->token_ = t;
      (*root)->parent_ = parent;
      root = &(*root)->siblings_;
      break;
    case XMLScanner::Token::Tag:
      *root = newNode();
      (*root)->token_ = t;
      (*root)->parent_ = parent;
      parse( *root, &(*root)->children_, s );
      root = &(*root)->siblings_;
      break;
    case XMLScanner::Token::Close:
      goto done;
    case XMLScanner::Token::Error:
    case XMLScanner::Token::EndOfFile:
      assert( !"this should not happen!" );
      goto done;
    }
  }
done:
  if( t.kind == XMLScanner::Token::Error && !error_ ) {
    error_ = newNode();
    error_->token_ = t;
  }
}

XMLNode * XMLDom::newNode()
{
  if( !nodesLeft_ ) {
    //  Don't grow exponentially in allocation.
    //  Growing by squared is good enough. This means 
    //  that we only waste, at most, sqrt(N) elements.
    nodesLeft_ = 128 * (1 + numBlocks_);
    XMLNode ** nub = new XMLNode *[ numBlocks_+1 ];
    memcpy( nub, nodes_, sizeof( XMLNode * ) * numBlocks_ );
    //TODO: this should probably be ::operator new() with memset!
    nub[numBlocks_] = new XMLNode[ nodesLeft_ ];
    nextNode_ = nub[numBlocks_];
    delete[] nodes_;
    nodes_ = nub;
    ++numBlocks_;
  }
  // TODO: placement new here
  --nodesLeft_;
  return nextNode_++;
}



XMLNode * XMLNode::operator[]( size_t ix ) const
{
  if( arrayIter_.ix > ix || !ix ) {
    arrayIter_.ix = 0;
    arrayIter_.node = children_;
  }
  while( arrayIter_.ix < ix && arrayIter_.node ) {
    ++arrayIter_.ix;
    arrayIter_.node = arrayIter_.node->siblings_;
  }
  return arrayIter_.node;
}

//  child() returns only attributes and child tags, possibly with specific name.
//  Note that these may have whitespace/cdata as siblings.
XMLNode * XMLNode::child( size_t ix )
{
  if( childIter_.ix > ix || !ix ) {
    childIter_.ix = 0;
    childIter_.node = children_;
    while( childIter_.node && 
        childIter_.node->token_.kind != XMLScanner::Token::Attribute && 
        childIter_.node->token_.kind != XMLScanner::Token::Tag ) {
      childIter_.node = childIter_.node->siblings_;
    }
  }
  while( childIter_.ix < ix && childIter_.node ) {
    childIter_.node = childIter_.node->siblings_;
    if( !childIter_.node ) {
      break;
    }
    if( childIter_.node->token_.kind == XMLScanner::Token::Attribute || 
        childIter_.node->token_.kind == XMLScanner::Token::Tag ) {
      ++childIter_.ix;
    }
  }
  return childIter_.node;
}

//  text() returns only whitespace and cdata.
//  Note that these may have tags as siblings (but not attributes).
XMLNode * XMLNode::text( size_t ix )
{
  if( textIter_.ix > ix || !ix ) {
    textIter_.ix = 0;
    textIter_.node = children_;
    while( textIter_.node && 
        textIter_.node->token_.kind != XMLScanner::Token::Whitespace && 
        textIter_.node->token_.kind != XMLScanner::Token::CDATA ) {
      textIter_.node = textIter_.node->siblings_;
    }
  }
  while( textIter_.ix < ix && textIter_.node ) {
    textIter_.node = textIter_.node->siblings_;
    if( textIter_.node->token_.kind == XMLScanner::Token::Whitespace|| 
        textIter_.node->token_.kind == XMLScanner::Token::CDATA ) {
      ++textIter_.ix;
    }
  }
  return textIter_.node;
}

XMLNode::XMLNode()
{
  children_ = 0;
  siblings_ = 0;
  parent_ = 0;
  arrayIter_.ix = 0xffffffff;
  childIter_.ix = 0xffffffff;
  textIter_.ix = 0xffffffff;
}


#if 0

static void recurse( XMLNode * n, bool closed )
{
  while( n ) {
    XMLScanner::Token const & t = n->token();
    switch( t.kind ) {
    case XMLScanner::Token::Attribute:
      assert( !closed );
      fprintf( stdout, " %.*s=\"%.*s\"", t.keySize, t.key, t.valueSize, t.value );
      break;
    case XMLScanner::Token::Tag:
      if( !closed ) {
        fprintf( stdout, ">" );
        closed = true;
      }
      fprintf( stdout, "<%.*s", t.keySize, t.key );
      recurse( (*n)[0], false );
      fprintf( stdout, "</%.*s>", t.keySize, t.key );
      break;
    case XMLScanner::Token::Whitespace:
    case XMLScanner::Token::CDATA:
      if( !closed ) {
        fprintf( stdout, ">" );
        closed = true;
      }
//      fprintf( stdout, "%.*s", t.valueSize, t.value );
      break;
    default:
      fprintf( stderr, "this should not happen!\n" );
      assert( !"error in recurse()" );
      break;
    }
    n = n->next();
  }
  if( !closed ) {
    fprintf( stdout, ">" );
    closed = true;
  }
  fprintf( stdout, "\n" );
}

int main( int argc, char * argv[] )
{
  if( argc < 2 ) {
    fprintf( stderr, "usage: xmlpp file ...\n" );
    return 1;
  }
  int errors = 0;
  for( int i = 1; i < argc; ++i ) {
    FILE * f = fopen( argv[i], "rb" );
    if( f == NULL ) {
      fprintf( stderr, "xmlpp: %s: cannot open\n", argv[i] );
      return 1;
    }
    fseek( f, 0, 2 );
    size_t len = ftell( f );
    fseek( f, 0, 0 );
    char * ptr = (char *)malloc( len );
    fread( ptr, 1, len, f );
    fclose( f );
    XMLDom dom( ptr, len );
    if( dom.error() != 0 ) {
      fprintf( stderr, "error: %s in %s\n", dom.error(), argv[i] );
      ++errors;
    }
    else {
      recurse( dom.root(), true );
    }
    free( ptr );
  }
  return errors;
}

#endif
